<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>图结构</title>
</head>
<body>
    <script src="dict.js"></script>
    <script src="queue.js"></script>
    <script>
        
        let queue = new Queue()
        class Graph {
            // 属性：顶点（数组）/边（字典）
            constructor() {
                this.vertexes = [] // 顶点
                let dict = new Dictionary()
                this.edges = dict // 边
            }
            
            // 方法

            // 添加方法
            // 1. 添加顶点
            addVertex(v) {
                this.vertexes.push(v)
                this.edges.set(v, [])
            }

            // 2. 添加边
            addEdge(v1, v2) {
                this.edges.get(v1).push(v2)
                this.edges.get(v2).push(v1)
            }

            toString() {
                let resultString = ''
                for (let i = 0; i < this.vertexes.length; i++) {
                    resultString += this.vertexes[i] + '-->'
                    let vEdges = this.edges.get(this.vertexes[i])
                    for (let j = 0; j < vEdges.length; j++) {
                        resultString += vEdges[j] + ' '
                    }
                    resultString += '\n'
                }
                return resultString
            }

            // 图的遍历：两种遍历算法，都需要明确指定第一个被访问的顶点
            // 1. BFS - Breadth-First Search - 广度优先搜索
            // 2. DFS - Depth-First Search - 深度优先搜索

            // 初始化状态颜色
            initializeColor() {
                let colors = []
                for (let i = 0; i < this.vertexes.length; i++) {
                    const v = this.vertexes[i];
                    colors[v] = 'white'
                }
                return colors
            }
            // 广度优先搜索 - BFS
            bfs(initV, handler) {
                // 1. 初始化颜色
                let colors = this.initializeColor()

                // 2. 创建队列
                let queue = new Queue()

                // 3. 将顶点加入到队列中
                queue.enQueue(initV)

                // 4. 循环从队列中取出元素
                while (!queue.isEmpty()) {
                    // 4.1 从队列取出一个顶点
                    let v = queue.deQueue()

                    // 4.2 获取和顶点相连的另外顶点
                    let vList = this.edges.get(v)

                    // 4.3 将v的颜色设置成灰色
                    colors[v] = 'gray'

                    // 4.4 遍历所有的顶点，并且加入到队列中
                    for (let i = 0; i < vList.length; i++) {
                        const e = vList[i];
                        if (colors[e] == 'white') {
                            colors[e] = 'gray'
                            queue.enQueue(e)
                        }
                    }

                    // 4.5 访问顶点
                    handler(v)

                    // 4.6 将顶点设置为黑色
                    colors[v] = 'black'
                }
            }

            // 深度优先搜索 - DFS
            dfs(initV, handler) {
                // 1. 初始化颜色
                let colors = this.initializeColor()

                this.dfsVisit(initV, colors, handler)
            }

            dfsVisit(v, colors, handler) {
                colors[v] = 'gray'

                handler(v)

                let vList = this.edges.get(v)
                for (let i = 0; i < vList.length; i++) {
                    const e = vList[i];
                    if (colors[e] == 'white') {
                        this.dfsVisit(e, colors, handler)
                    }
                }

                colors[v] = 'black'
            }
            
        }

        var graph = new Graph()

        myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
        for (let i = 0; i < myVertexes.length; i++) {
            const element = myVertexes[i];
            graph.addVertex(myVertexes[i])
        }
        graph.addEdge('A', 'B')
        graph.addEdge('A', 'C')
        graph.addEdge('A', 'D')
        graph.addEdge('C', 'D')
        graph.addEdge('C', 'G')
        graph.addEdge('D', 'G')
        graph.addEdge('D', 'H')
        graph.addEdge('B', 'E')
        graph.addEdge('B', 'F')
        graph.addEdge('E', 'I')
        console.log(graph.toString())

        // 测试bfs
        let result = ''
        graph.bfs(graph.vertexes[0], function (v) {
            result += v+ ' '
        })
        console.log(`广度优先搜索：${result}`)

        // 测试dfs
        result = ''
        graph.dfs(graph.vertexes[0], function (v) {
            result += v+ ' '
        })
        console.log(`深度优先搜索：${result}`)
    </script>
</body>
</html>